﻿package Classes {
	import Classes.Movement;
	import Classes.Coordinate;
	public class ABSearch {

	 	protected  static const FLAG_VALUE:int = 10000000;
		protected  static const WIN_VALUE:int = FLAG_VALUE-1000000;
		protected  static const MATE_VALUE:int = 10000000
		protected var nDistance:int;
        protected var board:Board;
        protected  var bestMove:Movement = null;
        private var boardArea:Array;
		private const  HASH_SIZE:int = 1 << 20; // 置换表大小
		private const  HASH_ALPHA:int = 1;      // ALPHA节点的置换表项
		private const  HASH_BETA:int = 2;       // BETA节点的置换表项
		private const  HASH_PV:int = 3;         // PV节点的置换表项
		private var sdPlayer:int = 0;
		private var nHashFlag:int;
		//用于重复局面检索
		protected var zobr:ZobristStruct=new ZobristStruct();
		protected var Zobrist:Table_Zobrist = new Table_Zobrist();
		protected var HashTable:Array = new Array();
		//History steps
		protected var mvsList:Array;
		private var nMoveNum:int;
		private static const MAX_MOVES:int = 255;
		private var offset:Array;
		private var stations:Array;
        public function ABSearch(b:Board):void {
            this.board = b;
			boardArea = board.ba;
			stations = board.getStations();
			zobr.InitZero();
			Zobrist.InitZobrist();
			initHistoryStep();
			initOffset();
        }
        
		public function resetAI()
		{
			nMoveNum = 0;
			sdPlayer = 0;
			nDistance = 0;
		}
		
		private function initHistoryStep()
		{
			mvsList = new Array();
			nMoveNum = 0;
			for(var i:int =0;i<MAX_MOVES;i++) {
				mvsList[i] = new MoveStruct();
			}
		}
        /**
         * All possible moves
         * @parameter true = NORTH / AI
         */
        public function possibleMoves(ai:Boolean):Array {
            var  moves:Array = new Array();
			var stations:Array = board.getStations();
			var boardArea:Array = board.ba;
            for (var j:int = 0 ; j < Board.BOARD_HEIGHT ; j++) {
                for (var i:int = 0; i < Board.BOARD_WIDTH; i++) {
                    if (ai && (Pieces.getLocated(board.ba[j][i]) == Pieces.AI_TAG) ||
                        !ai	&& (Pieces.getLocated(board.ba[j][i]) == Pieces.MAN_TAG)) {
                        //getMoves(j,i,moves);
						
						for (var tj:int = Board.BOARD_HEIGHT - 1; tj >=0; tj--) {
                            for (var ti:int = Board.BOARD_WIDTH -1; ti >=0; ti --){
							
                                var path:Array = board.pathFinding(i, j, ti, tj);
                                if (path != null && path.length > 0) {
									moves.push(new Movement(new Coordinate(j*100+ i), new Coordinate(tj*100+ti)));
                                }
                            }
                        }
                    }
                }
            }

            // Collections.sort(moves);
            // for (int i = 0; i < moves.size(); i++) {
            // logger.debug(moves.get(i));
            // }
			
            return moves;
        }
        
        /**
         * Evaluation, @parameter true = NORTH / AI
         */
        public function evaluation(ai:Boolean):int {
            var stations:Array = board.getStations();
            var ba:Array = board.ba;
            var value:int = 0;
            for (var j:int = 0; j < Board.BOARD_HEIGHT; j++) {
                for (var i:int = 0; i < Board.BOARD_WIDTH; i++) {
                    // 子力加和分数
                    if (ba[j][i] == Pieces.SILING_N) {
                        value += 350;
                    } else if (ba[j][i] == Pieces.JUNZHANG_N) {
                        value += 260;
                    } else if (ba[j][i] == Pieces.SHIZHANG_N) {
                        value += 170;
                    } else if (ba[j][i] == Pieces.LVZHANG_N) {
                        value += 120;
                    } else if (ba[j][i] == Pieces.TUANZHANG_N) {
                        value += 90;
                    } else if (ba[j][i] == Pieces.YINGZHANG_N) {
                        value += 70;
                    } else if (ba[j][i] == Pieces.LIANZHANG_N) {
                        value += 40;
                    } else if (ba[j][i] == Pieces.PAIZHANG_N) {
                        value += 20;
                    } else if (ba[j][i] == Pieces.GONGBING_N) {
                        value += 130;
                    } else if (ba[j][i] == Pieces.MINE_N) {
                        value += 60;
                    } else if (ba[j][i] == Pieces.BOMB_N) {
                        value += 39;
                    } else if (ba[j][i] == Pieces.FLAG_N) {
                        value += FLAG_VALUE;
                    } else if (ba[j][i] == Pieces.SILING_S) {
                        value -= 350;
                    } else if (ba[j][i] == Pieces.JUNZHANG_S) {
                        value -= 260;
                    } else if (ba[j][i] == Pieces.SHIZHANG_S) {
                        value -= 170;
                    } else if (ba[j][i] == Pieces.LVZHANG_S) {
                        value -= 120;
                    } else if (ba[j][i] == Pieces.TUANZHANG_S) {
                        value -= 90;
                    } else if (ba[j][i] == Pieces.YINGZHANG_S) {
                        value -= 70;
                    } else if (ba[j][i] == Pieces.LIANZHANG_S) {
                        value -= 40;
                    } else if (ba[j][i] == Pieces.PAIZHANG_S) {
                        value -= 20;
                    } else if (ba[j][i] == Pieces.GONGBING_S) {
                        value -= 60;
                    } else if (ba[j][i] == Pieces.BOMB_S) {
                        value -= 130;
                    } else if (ba[j][i] == Pieces.MINE_S) {
                        value -= 39;
                    } else if (ba[j][i] == Pieces.FLAG_S) {
                        value -= FLAG_VALUE;
                    }
                    
                    // 旗左右的位置是killer招法，这主要弥补搜索深度的不足
                    if (ba[j][i] == Pieces.FLAG_S
						&& (Pieces.getLocated(ba[j][i + 1])== Pieces.AI_TAG ||Pieces.getLocated(ba[j][i - 1])== Pieces.AI_TAG)) {
                        value += FLAG_VALUE / 100;
                    } else if (ba[j][i] == Pieces.FLAG_N
                               && (Pieces.getLocated(ba[j][i + 1])== Pieces.MAN_TAG ||Pieces.getLocated(ba[j][i - 1])== Pieces.MAN_TAG)) {
                        value -= FLAG_VALUE / 100;
                    }
                    
                    // 要破三角雷
                    if (ba[j][i] == Pieces.FLAG_N
						&& ba[j][i + 1] == Pieces.MINE_N
						&& ba[j][i - 1] == Pieces.MINE_N
						&& ba[j + 1][i] == Pieces.MINE_N) {
                        value += 220;
                    } else if (ba[j][i] == Pieces.FLAG_S
                               && ba[j][i + 1] == Pieces.MINE_S
                               && ba[j][i - 1] == Pieces.MINE_S
                               && ba[j - 1][i] == Pieces.MINE_S) {
                        value -= 220;
                    }
                    
                    // 不要进非旗的大本营
                    if (stations[j][i] == Board.HEADQUARTER && Pieces.getLocated(ba[j][i])== Pieces.AI_TAG ) {
                        value -= 100;
                    } else if (stations[j][i] == Board.HEADQUARTER && Pieces.getLocated(ba[j][i])== Pieces.MAN_TAG) {
                        value += 100;
                    }
                    
                    // 占对方旗上的行营，这个位置很重要
                    if (ba[j][i] == Pieces.FLAG_S && Pieces.getLocated(ba[j - 2][i])== Pieces.AI_TAG ){
                        value += 25;
                    } else if (ba[j][i] == Pieces.FLAG_N && Pieces.getLocated(ba[j + 2][i])== Pieces.MAN_TAG ){
                        value -= 25;
                    }
                    
                    // 旗上面的位置也很重要
                    if (ba[j][i] == Pieces.FLAG_S && Pieces.getLocated(ba[j - 1][i])== Pieces.AI_TAG) {
                        value += 20;
                    } else if (ba[j][i] == Pieces.FLAG_N && Pieces.getLocated(ba[j + 1][i])== Pieces.MAN_TAG) {
                        value -= 20;
                    }
                    
                    // 攻占对方底线加分（鼓励进攻和加强防守）
                    if (j == 10 && Pieces.getLocated(ba[j][i])== Pieces.AI_TAG) { 
                        value += 8;
                    } else if (j == 1 &&  Pieces.getLocated(ba[j][i])== Pieces.MAN_TAG) {
                        value -= 8;
                    }
                    
                    // 其他行营占分
                    if (stations[j][i] == Board.CAMP && Pieces.getLocated(ba[j][i])== Pieces.AI_TAG) { 
                        value += 5;
                    } else if (stations[j][i] == Board.CAMP && Pieces.getLocated(ba[j][i])== Pieces.MAN_TAG) {
                        value -= 5;
                    }
                }
            }
            
            if (ai==false) { // 负值最大搜索。对当前一方而言，如果占优则返回正数，否则返回负数
                value = -value;
            }
            return value;
        }
        
        /**
         * True if game is over.
         */
        public function isGameOver(player:Boolean):Boolean {
            return evaluation(player) > ABSearch.FLAG_VALUE / 2;
        }
        
        /**
         * Alpha-beta search
         */
        public function alphaBeta(depth:int,player:Boolean,alpha:int,beta:int):int {
            if (depth == 0 || isGameOver(player)) {
                return evaluation(player);
            }
            
			
    		var vl:int = ProbeHash(alpha, beta, depth, null);
    		if (vl > -MATE_VALUE) {
       			//trace("ProbeHash:"+vl);
        		return vl;
    		}
			
            var moves:Array = possibleMoves(player);
			nHashFlag = HASH_ALPHA;
			var mvBest = 0;
			var vlBest:int = -MATE_VALUE; // 这样可以知道，是否一个走法都没走过(杀棋)
            for (var i:int = 0; i < moves.length; i++) {
                var mm:Movement = moves[i];
           		MakeMove(mm);
                var value:int = - alphaBeta(depth - 1, !player, -beta, -alpha);
                UndoMakeMove();
				if(value > vlBest) {
					vlBest = value;
					
					if (value >= beta) {
						nHashFlag = HASH_BETA;
                		mvBest = mm.toInteger();
                   	 	break;
                	}
                	if (value >= alpha) {
						mvBest = mm.toInteger();
						nHashFlag = HASH_PV;
						alpha = value;     // 缩小Alpha-Beta边界
                	}
                	
				}
            }
			RecordHash(nHashFlag,vlBest,depth,mvBest);

            return vlBest;
        }
		
		public function aiMove():void {
			var rint:int = Math.random()*100;
			var depth:int = 0;
			if (rint < 35) { 
				depth = 0;	// 35%
			} else if (rint < 80) {
				depth = 1;	// 45%
			} else {
				depth = 2;	// 20%
		    }
			depth = 2;	
			trace("Search depth:" +depth);
		
			  // 1-3. 尝试置换表裁剪，并得到置换表走法
			HashTable.length = 0;
			var moves:Array = possibleMoves(true);
			trace(moves.length);
			var values:Array = new Array();
			var m:Movement;
			for(var k=0;k<moves.length;k++) {
				m = moves[k];
				trace(m.getStart().y +" "+ m.getStart().x+" -> "+m.getEnd().y +" "+m.getEnd().x);
			}

			// 先做一下局面评估
			
			for (var i:int = 0; i < moves.length; i++) {
				var mm:Movement = moves[i];
				values[i] = int.MAX_VALUE;
				MakeMove(mm);
				mm.setValue(evaluation(true));
				UndoMakeMove();
				if(mm.getValue() > WIN_VALUE){
					var s:Coordinate = mm.getStart();
					var e:Coordinate = mm.getEnd();
					board.robotMove(s.y,s.x,e.y,e.x);
					return;
				}
			}

			moves.sort(sortBaseValue);

			for (i = 0; i < moves.length; i++) {
				mm = moves[i];
				sPos = mm.getStart();
				ePos = mm.getEnd();
			}
			
			for (i = 0; i < moves.length ; i++) {
				mm = moves[i];
				MakeMove(mm);
				values[i] = alphaBeta(depth, false, int.MIN_VALUE,
					int.MAX_VALUE);
				UndoMakeMove();
			}

			var chosen:int = 0;	// 电脑选择的步骤
			var min:int = int.MAX_VALUE;
			for (i = 0; i < values.length; i++) {
				if (values[i] < min) {
					chosen = i; // 电脑选择对Human来说估值最小的move
					min = values[i];
				}
			}
			var aiAction:Movement = moves[chosen];
			// 电脑采取行动
			var sPos:Coordinate = aiAction.getStart();
			var ePos:Coordinate = aiAction.getEnd();
			board.robotMove(sPos.y,sPos.x,ePos.y,ePos.x);
			trace(sPos.y+" "+sPos.x+" -> "+ePos.y+" "+ePos.x);
			//RecordHash(HASH_PV, vlBest, nDepth, Search.mvResult);
		}
		
		function sortBaseValue(a:Movement,b:Movement):Number{
			return a.getValue()<b.getValue()?1:-1;
		}
		
		private function RecordHash(nFlag:int,vl:int,nDepth:int,mv:int):void {
    		var hsh:HashItem ;
   			hsh = HashTable[zobr.dwKey & (HASH_SIZE - 1)];
			//
			if(hsh == null) {
				HashTable[zobr.dwKey & (HASH_SIZE - 1)] = new HashItem();
				hsh = HashTable[zobr.dwKey & (HASH_SIZE - 1)];
			}
    		//当前记录的深度更大时 没必要记录
    		if (hsh.ucDepth > nDepth) {
        			return;
    		}
   			hsh.ucFlag = nFlag;
    		hsh.ucDepth = nDepth;
    		if (vl > WIN_VALUE) {
        		if (mv == 0) {
            		return; // 可能导致搜索的不稳定性，并且没有最佳着法，立刻退出
       	 		}
        		hsh.svl = vl + nDistance;
    		} 
			else if (vl < -WIN_VALUE) {
        		if (mv == 0) {
            	return; // 同上
        		}
        		hsh.svl = vl - nDistance;
    		} 
			else {
       			 hsh.svl = vl;
    		}
    		hsh.wmv = mv;
    		hsh.dwLock0 = zobr.dwLock0;
    		hsh.dwLock1 = zobr.dwLock1;
    		HashTable[zobr.dwKey & (HASH_SIZE - 1)] = hsh;
		}
		
		public function ProbeHash(vlAlpha:int,vlBeta:int,nDepth:int,mv:Movement):int {
   			 var bMate:Boolean; // 杀棋标志：如果是杀棋，那么不需要满足深度条件
    		 var hsh:HashItem;
    
    		 hsh = HashTable[zobr.dwKey & (HASH_SIZE - 1)];
			 if(hsh == null) return -MATE_VALUE 
    		if (hsh.dwLock0 != zobr.dwLock0 || hsh.dwLock1 != zobr.dwLock1) {
        		//mv.parseMoveInteger(0);
        		return -MATE_VALUE;
    		}
			if(mv != null) {
    			mv.parseMoveInteger(hsh.wmv);
			}
    		bMate = false;
    		if (hsh.svl > WIN_VALUE) {
        		hsh.svl -= nDistance;
        		bMate = true;
    		} else if (hsh.svl < -WIN_VALUE) {
       			 hsh.svl += nDistance;
        		bMate = true;
    		}
    		if (hsh.ucDepth >= nDepth || bMate) {
        		if (hsh.ucFlag == HashItem.HASH_BETA) {
            		return (hsh.svl >= vlBeta ? hsh.svl : -MATE_VALUE);
        		} else if (hsh.ucFlag == HashItem.HASH_ALPHA) {
            		return (hsh.svl <= vlAlpha ? hsh.svl : -MATE_VALUE);
       	 		}
        		return hsh.svl;
    		}	
    		return -MATE_VALUE;
		}
		
		// 交换走子方
		private function ChangeSide():void 
		{   
    		sdPlayer = 1 - sdPlayer;
    		zobr.Xor(Zobrist.Player);
		}
		
		public function MakeMoveRC(srcRow:int,srcCol:int,dstRow:int,dstCol:int)
		{
			var ms:MoveStruct = mvsList[nMoveNum];
			ms.srcRow = srcRow;
			ms.srcCol = srcCol;
			ms.dstRow = dstRow;
			ms.dstCol = dstCol;
			ms.srcChess = boardArea[ms.srcRow][ms.srcCol] ;
			ms.dstChess = boardArea[ms.dstRow][ms.dstCol];
			ChangeSide();
			nDistance++;
			nMoveNum++;
							
		}
		
		private function MakeMove(mv:Movement):void
		{
			var ms:MoveStruct = mvsList[nMoveNum];
			ms.srcRow = mv.getStart().y;
			ms.srcCol = mv.getStart().x;
			ms.dstRow = mv.getEnd().y;
			ms.dstCol = mv.getEnd().x;
			ms.srcChess = boardArea[ms.srcRow][ms.srcCol] ;
			ms.dstChess = boardArea[ms.dstRow][ms.dstCol];
			board.makeaMove(mv);
			ChangeSide();
			nDistance++;
			nMoveNum++;
		}
		
		private function UndoMakeMove():void
		{                   // 撤消走一步棋
    		nDistance--;
    		nMoveNum--;
    		ChangeSide();
    		var ms:MoveStruct = mvsList[nMoveNum];
			var srcChess:int = ms.srcChess;
			var dstChess:int = ms.dstChess;
			//yfxu
			DelPiece(ms.dstRow,ms.dstCol);
			if(srcChess != Board.INVALID_BOARD_TAG) {
				AddPiece(ms.srcRow,ms.srcCol,srcChess);
			}
			if(dstChess != Board.INVALID_BOARD_TAG) {
				AddPiece(ms.dstRow,ms.dstCol,dstChess);
			}

		}
		
		public function AddPiece(row:int,col:int,chess:int)
		{
			if(chess == 0) return;
			boardArea[row][col] = chess;
			var cs:int;
			if(chess<=0x0D) cs = chess - 2;
			if(chess>0x10) cs = chess-6;
			//if(cs<0||cs>23) {
				//trace("range over array[0-11]");
				//return;
			//}
			var zs:ZobristStruct = Zobrist.Table[cs][row][col];
			zobr.Xor(zs);
		}
		
		public function DelPiece(row:int,col:int)
		{
			var chess:int = boardArea[row][col];
			if(chess == 0) return;
			boardArea[row][col] = 0;
			var cs:int;
			if(chess<=0x0D) cs = chess - 2;
			else if(chess>0x10) cs = chess-6;
			//if(cs<0||cs>23) {
				//trace("range over array[0-11]");
				//return;
			//}
			var zs:ZobristStruct = Zobrist.Table[cs][row][col];
			zobr.Xor(zs);
		}
		
		public function printZobr()
		{
			trace((zobr.dwKey&(this.HASH_SIZE-1))+" "+zobr.dwLock0 + "   "+zobr.dwLock1);
		}
		
		public function getMoves(row:int,col:int,moves:Array)
		{
			if(boardArea[row][col] == Board.INVALID_BOARD_TAG) return;
			//chess in the headquarter cannot be moved
			if(stations[row][col] == Board.HEADQUARTER) return;
			var chess:int = boardArea[row][col];
			var type:int = Pieces.getPureType(chess);
			
			//flag and mine cannot be moved
			if(type == Pieces.FLAG_S || type == Pieces.MINE_S) return;
			
			var bOnRailway:Boolean = (stations[row][col] == Board.STATION_RAILWAY);
			var sq:int = row*5+col;
			var chessOffset:Array = offset[sq];
			var curR = row;
			var curC = col;
			if(col>4)return;
			
			for(var i:int =0;i<chessOffset.length/2;i++) {
				var oR = chessOffset[i*2];
				var oC = chessOffset[i*2+1];
				curR = row;
				curC = col;
				curR = curR+ parseInt(oR);
				curC = curC +parseInt(oC);
				if(curR<0||curR>11||curC<0||curC>4) continue;
				var dstChess = boardArea[curR][curC];
				if(canMove(chess,dstChess)==true) {
					if(stations[curR][curC] == Board.CAMP && dstChess != 0) {
						
					}
					else if(stations[curR][curC] == Board.CAMP && dstChess == 0) {
						moves.push(new Movement(new Coordinate(row*100+col),new Coordinate(curC+100*curR)));
					}
					else 
					{	
						moves.push(new Movement(new Coordinate(row*100+col),new Coordinate(curC+100*curR)));
					}
				}
				//if onrailways
				if(bOnRailway) {
					if(dstChess != Pieces.INVALID) continue;
					curR = curR+oR;
					curC = curC +oC;
					if(curR<0||curR>11||curC<0||curC>4) continue;

					dstChess = boardArea[curR][curC];
					
					while(stations[curR][curC] == Board.STATION_RAILWAY&&canMove(chess,dstChess)==true) {
						if(stations[curR][curC] == Board.CAMP && dstChess != Board.INVALID_BOARD_TAG) {
						
						}
						else 
						{	
							
							moves.push(new Movement(new Coordinate(row*100+col),new Coordinate(curC+100*curR)));
						}
						if(dstChess != Pieces.INVALID) return;
						curR = curR+oR;
						curC = curC +oC;
						if(curR<0||curR>11||curC<0||curC>4) break;
						dstChess = boardArea[curR][curC];
					}
				}
				
			}
			
		}
		
		private function canMove(chessA:int,chessB:int):Boolean
		{
			if(chessB==0)return true;
			else if(chessA<=0x0D &&chessA>0 && chessB<=0x0D && chessB>0) return false;
			else if(chessA>0x10 && chessB > 0x10) return false;
			return true;
		}
		
		public function initOffset()
		{
			offset = new Array();
			offset[0] = [1,0,0,1];
			offset[1] = [0,-1,1,0,0,1];
			offset[2] = [0,-1,1,0,0,1];
			offset[3] = [0,-1,1,0,0,1];
			offset[4] = [0,-1,1,0];

			offset[5] = [1,0,1,1,0,1,-1,0];
			offset[6] = [0,-1,1,0,0,1,-1,0];
			offset[7] = [0,-1,1,-1,1,0,1,1,0,1,-1,0];
			offset[8] = [0,-1,1,0,0,1,-1,0];
			offset[9] = [0,-1,1,0,1,-1];

			offset[10] = [1,0,0,1,-1,0];
			offset[11] = [0,-1,1,-1,1,0,1,1,0,1,-1,1,-1,0,-1,-1];
			offset[12] = [0,-1,1,0,0,1,-1,0];
			offset[13] = [0,-1,1,-1,1,0,1,1,0,1,-1,1,-1,0,-1,-1];
			offset[14] = [1,0,0,-1,-1,0];

			offset[15] = [1,0,0,1,-1,0,-1,1,1,1];
			offset[16] = [0,-1,1,0,0,1,-1,0];
			offset[17] = [0,-1,1,-1,1,0,1,1,0,1,-1,1,-1,0,-1,-1];
			offset[18] = [0,-1,1,0,0,1,-1,0];
			offset[19] = [1,0,0,-1,-1,0,-1,-1,1,-1];

			offset[20] = [1,0,0,1,-1,0];
			offset[21] = [0,-1,1,-1,1,0,1,1,0,1,-1,1,-1,0,-1,-1];
			offset[22] = [0,-1,1,0,0,1,-1,0];
			offset[23] = [0,-1,1,-1,1,0,1,1,0,1,-1,1,-1,0,-1,-1];
			offset[24] = [1,0,0,-1,-1,0];

			offset[25] = [1,0,0,1,-1,1,-1,0];
			offset[26] = [0,-1,0,1,-1,0];
			offset[27] = [0,-1,1,0,0,1,-1,1,-1,0,1,-1];
			offset[28] = [0,-1,0,1,-1,0];
			offset[29] = [0,-1,1,0,-1,0,-1,-1];
			
			for(var i=0;i<30;i++){
				var srcOffset:Array = offset[i];
				var dstOffset:Array = new Array;
				for(var j=0;j<srcOffset.length;j++) {
					dstOffset.push(srcOffset[j]*-1);
				}
				offset[59-i] = dstOffset;
			}
		}
		
	}
	
}
